home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor1 / msort.doc < prev    next >
Text File  |  1995-03-31  |  3KB  |  59 lines
  1. MARK SORT by Jeremy Hawdon, HPCC #600 
  2. Published in DATAFILE V9 N3, April/May 1990, p.22 
  3.  
  4. This program sorts an array, list or stack of integers returning to level 1 
  5. a list sorted in descending order.  The type statements at the beginning of 
  6. the program turn a list or stack of numbers into a vector.  The array is 
  7. sorted in two passes into "range + 1" lists on the stack which are then 
  8. concatenated. 
  9.  
  10. There is a speed advantage over other sorting programs when sorting a large 
  11. number of integers with a relatively small range of values.  For example in 
  12. sorting 100 integers with values from 0 to 20 sorting times were as follows: 
  13.  
  14.          MSORT     18.4 s 
  15.          PSORT     49.7 s 
  16.          GSORT     74.6 s 
  17.          BSORT    362.2 s 
  18.  
  19. PSORT is a numerical pigeon sort program, which sorts a list of n numbers 
  20. into n + 1 lists on the stack in a way quite similar to MSORT, then sorts 
  21. those lists recursively and recombines the sorted lists into a single list. 
  22.  
  23. GSORT is the general purpose sort program from William C. Wickes' excellent 
  24. book "HP-28 Insights"; a version of the Quicksort algorithm.  The program 
  25. to time the sorts also came from this book. 
  26.  
  27. BSORT is the Bubble Sort program by G. Miles (DATAFILE V7 N6) slightly 
  28. amended to accept and return a list. 
  29.  
  30. -- Jeremy Hawdon 
  31. --------------------------------------------------------------------------- 
  32. Additional notes by Joseph K. Horn: 
  33.  
  34. Jeremy wrote this for the HP 28.  I changed the two LIST-> commands 
  35. to OBJ-> for the HP 48.  HP 28 fans can change them back if they wish. 
  36.  
  37. Jeremy mentions that this program is fast when the data range is small; it 
  38. is unfortunate that when the data range is large, it really bogs down, and 
  39. requires a lot of memory, due to the way it creates "range + 1" lists on 
  40. the stack.  For example, the list {1 n n n 1 1 1 n n 1 n 1 1 1 n} with the 
  41. following values for n is sorted in this much time: 
  42.  
  43.           n      time 
  44.           2      1.8 s 
  45.          10      2.0 s 
  46.         100      4.5 s 
  47.        1000     30.8 s 
  48.       10000    294.0 s  (4 min 54 sec) 
  49.  
  50. When I tried to use n=100000, after a long time it ran out of memory 
  51. ("Insufficient Memory" error), even though there was over 100K MEM at the 
  52. start. 
  53.  
  54. Also, the program only sorts the integer part.  The list {2.3 2.2 3.2 3.3} 
  55. is "sorted" into {3.2 3.3 2.3 2.2}.  The fractional parts are ignored. 
  56.  
  57. The moral is: use this program only when you only have integers (or don't 
  58. care about the fractional part), and when the data range is small.  -jkh- 
  59.